This description relates to indexing stored data.
Data records in a relational database management system (RDBMS) are maintained in tables, which are a collection of rows all having the same columns. Each column maintains information on a particular type of data for the data records which include the rows. One or more indexes may be associated with each table. An index is an ordered set of pointers to data records in the table based on the data in one or more columns of the table. An index includes rows or index entries which include an index key and a pointer to a database record in the table having the key column values of the index entry key.
Index entries are often stored in a B-tree data structure. A B-tree includes a single root node and a number of leaf and branch nodes. The leaf nodes store the index entries. Each index entry includes key values and the physical address or identifier of the row or record in the database table which has the key values in its key columns. A branch node stores key values and pointers to other branch nodes. An index may be searched for matching key values by an index scan. A scan of the index traverses from the root node down to the leaf node looking for the index entries that have the matching keys. The nodes which store the index entries are maintained in a storage device, such as a hard disk drive or other non-volatile memory accessible to the database program.
A query can be made against an index to retrieve one or more index keys using a search key that includes values for each of the key columns. The search locates the first index entry that has a key value that matches the search key, i.e., the values in the key columns in the search key match the values for the key columns in the index entry.